// 深度优先搜索（DFS） 算法

// 核心思想：
// 遍历网格，当遇到 '1' 时，表示发现一个新岛屿。
// 使用 DFS 递归淹没（标记为 '0'）所有相连的陆地，确保它们不会被重复计数。

// DFS 淹没过程：
// 终止条件：超出网格边界或当前单元格不是 '1'。
// 操作：将 '1' 改为 '0'（防止重复访问）。
// 递归方向：上、下、左、右四个方向。

// 复杂度分析：
// 时间复杂度：O(m×n)，每个单元格最多访问两次（一次检查，一次淹没）。
// 空间复杂度：O(m×n)，递归栈的深度在最坏情况下可能达到网格大小。


function numIslands(grid) {
  if (!grid || grid.length === 0) return 0;

  let count = 0;
  const rows = grid.length;
  const cols = grid[0].length;

  // DFS 淹没当前岛屿
  const dfs = (i, j) => {
    // 边界检查 + 是否为陆地检查
    if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] !== '1') return;

    grid[i][j] = '0'; // 淹没当前陆地

    // 递归淹没四个方向的相邻陆地
    dfs(i + 1, j); // 下
    dfs(i - 1, j); // 上
    dfs(i, j + 1); // 右
    dfs(i, j - 1); // 左
  };

  // 遍历整个网格
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === '1') {
        count++;        // 发现新岛屿
        dfs(i, j);      // 淹没整个岛屿
      }
    }
  }

  return count;
}